package leetcode_题库;

/**
 * Created by IntelliJ IDEA.
 *
 * @ProjectName leetcode
 * @Author Ding
 * @CreateTime 2022/8/24 10:41 星期三
 */
public class _203_移除链表元素 {
    public static void main(String[] args) {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(6);
        ListNode n4 = new ListNode(3);
        ListNode n5 = new ListNode(4);
        ListNode n6 = new ListNode(5);
        ListNode n7 = new ListNode(6);

//        ListNode n1 = new ListNode(7);
//        ListNode n2 = new ListNode(7);
//        ListNode n3 = new ListNode(7);
//        ListNode n4 = new ListNode(7);
//
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n6;
        n6.next = n7;

//        ListNode nn = removeElements(n1,6);
        ListNode nn = removeElementsQuick(n1, 6);
//        ListNode nn = removeElementsQuick(n1,7);
        while (nn != null) {
            System.err.println(nn.val);
            nn = nn.next;
        }
    }

    /**
     * 不设置虚拟结点，维护两个结点进行On遍历，空间提交时耗费稍大，但尚可。
     * > 2022/08/24 14:14:12
     * 解答成功:
     * 	执行耗时:0 ms,击败了100.00% 的Java用户
     * 	内存消耗:42.3 MB,击败了42.58% 的Java用户
     * @param head
     * @param val
     * @return
     */
    private static ListNode removeElementsQuick(ListNode head, int val) {
        if (head == null) {
            //首结点为空，直接返回null（不要反悔new ListNode()，若如此，结点不为null且val初始值为0）
            return null;
        }
        //维护变量preN，作为遍历结点的前一个结点
        ListNode preN = head;
        //维护变量N，作为每次遍历的结点
        ListNode stepN = head.next;
        //没遍历完，就继续循环
        while (stepN != null) {
            if (stepN.val == val) {
                //是目标值，让preN的next指向step的next
                preN.next = stepN.next;
            } else {
                //否则，preN称为stepN（别慌，马上就让stepN走了）
                preN = stepN;
            }
            //不论如何，step走一步
            stepN = stepN.next;
        }
        //若头结点也是val，返回其下一结点，否则返回本身
        return head.val == val ? head.next : head;
    }

    /**
     * 哑结点法，所有不是待删除元素，都链到一个新结点中
     * 由于一般待删除元素较少，所以多次插入性能大部分都会很差。
     * > 2022/08/24 10:57:56
     * 解答成功:
     * 执行耗时:1 ms,击败了50.01% 的Java用户
     * 内存消耗:42.4 MB,击败了30.51% 的Java用户
     *
     * @param head
     * @param val
     * @return
     */
    public static ListNode removeElements(ListNode head, int val) {
        //定义哑结点，初始值随便一个-1（不返回）
        ListNode dumbNode = new ListNode(-1);
        //定义动态结点p充当哑结点的尾结点
        ListNode p = dumbNode;
        //若头结点不为空（没遍历完）
        while (head != null) {
            //若值不是待删除元素
            if (head.val != val) {
                //仅赋值（切记不要p.next = head），这样会带走head的所有后续结点
                p.next = new ListNode(head.val);
                //动态尾结点右移
                p = p.next;
            }
            //无论如何，head右移
            head = head.next;
        }
        //返回哑结点的后续结点
        return dumbNode.next;
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
